Fritz: All Fritz/All Fritz.zip/All Fritz/FILES/PROGSCAL/BTREE4.LZH/BTREE4.DOC

Text File | 1988-01-17 | 26KB | 661 lines

                                  BTREE4

                a Shareware Unit for Turbo Pascal ver. 4.0

                    for Data and Index file management


                    Copyright (c) 1988 by W. Lee Passey











                             Pass-Key Software
                            119 MacArthur Ave.
                         Salt Lake City, UT  84115
                          [phone] (voice)
                          [phone] (data)






















     BTree4 is  a separately  compiled unit  for Turbo  Pascal ver. 4.0 from
Borland International, Inc. BTree4  may be  linked to  a user's  source pro-
grams,  and  will  performs  all  of  the  same B-tree indexing functions as
Borland's Database Toolbox.

     This file contains general information about BTree4, an  annotated copy
of the  interface segment  describing all variables and procedures available
to calling procedures, and licensing and  registration information.   PLEASE
READ THIS FILE COMPLETELY BEFORE ATTEMPTING TO USE BTREE4.

BTree4  has  been  designed  to  be as compatible as possible with Borland's
Database Toolbox, but it  is not  a modification  of Borland's  source code;
rather it  is a whole new set of procedures and functions using a compatible
calling interface, but a wholly different memory storage  technique.  BTree4
does not require any pre-defined constants or initializaton sequence, as all
data storage, including the index page  stack, is  created as  needed on the
heap.

     For maximum  flexibility, the BTree4 routines will not halt the program
for any IO or heap full errors.  If an error is detected, the global boolean
variable 'OK'  is set to false, and the global integer variable 'IOError' is
set equal to the IO error code.   If the  error was  caused by  the unavail-
ability of heap memory, 'IOError' will be set to -1.

     Disk  IO  errors  must  be  resolved  by the programmer, however memory
allocation errors can usually  be  resolved  by  the  use  of  the procedure
'CheckMem'   in   conjunction   with   the   global  variable  'MaxPageMem.'
'MaxPageMem' should be set by the programmer to  the maximum  amount of heap
memory which  will be allocated for the index page stack.  If the page stack
attempts to exceed this amount of allocated memory,  little used  pages will
be discarded from memory until the page stack is again under the limit.  The
program expects that the amount of memory available will never  be less than
the value stored in 'MinPageMem', and the stack size will never be decreased
to less than that  value; thus,  'MaxPageMem' should  always be  larger than
'MinPageMem.'

     Both 'MaxPageMem'  and 'MinPageMem'  can be dynamically assigned values
at any time during the operation of the program.  If more  dynamic memory is
needed,  the  page  stack  can  be  reduced in size by reducing the value of
'MaxPageMem' (and 'MinPageMem', if necessary) and then calling CheckMem with
a zero  parameter.  The only restriction is that 'MinPageMem' must always be
large enough to hold one page from each  level of  the tree,  plus one extra
page.

     In  addition  to  the  page  stack,  each open data file and index file
allocates for itself an IO buffer equal in size to the file's record length,
and each  index file  allocates an extra page buffer which is the same size.
These buffers are de-allocated  only by  closing the  associated file.   The
record length  for index  files is  equal to  5 + (number of keys per page X
(key length + 9)).

     What follows is a copy  of  the  BTree4  interface  section,  with each
procedure and significant variable annotated as to its function and use.













{$I-,V-}

unit btree4;                      { VERSION 1.0 }
                                  { Copyright (c) 1988 by W. Lee Passey }
interface

type
  MaxString   = string[255];
  bufarray    = array [1..80] of byte;
  Str80       = string[80];

  PagePtr     = ^PageHeader;
  KeyListPtr  = ^KeyList;

  DataFile    = record
    case byte of
      0 : (F      : file);
      1 : (Handle,
           Mode,
           RecSize    : word;
           Private    : array [1..26] of byte;        { reserved by TP4 }
           FirstFree,         { the first available record in the file  }
           NumberFree : longint;   { the number of records deleted and
                                     therefore available for use        }
           RecLength  : word;      { the length of records in this file }
           KeysPerPage,            { if an index file, the maximum number
                                     of keys which may be put on a page }
           KeyLength  : byte;      { if an index file, the maximum
                                     length of a key                    }
           FirstPage  : longint;   { if an index file, the number of the
                                     record which is the root page      }
           FileName   : array [1..80] of char;
           Buffer     : ^BufArray);{ pointer to a buffer on the heap,
                                     used with this file, whose size is
                                     identical to the record length     }
           end;

  IndexFile   = record
    DF        : DataFile;
    RootPage  : PagePtr;           { a pointer to the root page, if it
                                     is in memory                       }
    KeySize,                       { the size of a key record, on the
                                     heap, for keys in this file        }
    ItemSize  : word;              { the size of a key, its reference
                                     and record pointer, in this file   }
    SavePage  : PagePtr;
    SaveKey   : KeyListPtr;
    SaveRec   : longint;
    PageBuffer: ^BufArray;        { pointer to a buffer on the heap,
                                    used with this file, whose size is
                                    identical to the record length, and
                                    which is used for packing and
                                    unpacking pages to and from the disk












                                    and memory.                         }
    end;

(*   Like Borland's Database Toolbook, each file use by BTree4 must be
declared either as a DataFile or an IndexFile.  *)

  PageHeader  = record
    NextPage,                     { these two pointers link the pages   }
    PrevPage,                     { into a two-way linked list in memory
                                    each time a page is used it is placed
                                    back at the head of this list       }
    ParentPage,                   { a pointer to this page's parent page
                                    which should be in memory           }
    GreaterPage : PagePtr;        { a pointer to a page on a lower level
                                    containing keys greater than all
                                    keys on this page, if in memory     }
    GreaterRec,                   { the disk record number of the page
                                    which goes in GreaterPage           }
    RecNum      : longint;        { the disk record number of this page }
    FilePtr     : ^IndexFile;     { points to the file variable of the
                                    file which this page comes from     }
    ParentKey,                    { the key record from the parent page
                                    which contains the key which is one
                                    greater than all the keys on this
                                    page.  if this pointer is nil, you
                                    must go up another page; if this is
                                    not possible you are in the root
                                    page.                               }
    KeyList,                      { pointer to the first key on page    }
    ListEnd     : KeyListPtr;     { pointer to the last key on page     }
    KeysOnPage  : byte;           { the number of keys actually in the
                                    key list and on the page            }
    end;

  KeyList     = record
    NextKey,                      { these are the link pointers for the }
    PrevKey     : KeyListPtr;     { list of keys                        }
    LesserPage  : PagePtr;        { a pointer to a page on a lower level
                                    containing keys less than all keys
                                    on this page, if in memory          }
    LesserRec,                    { the disk record number of the page
                                    which goes into LesserPage          }
    Reference   : longint;        { the data reference associated with
                                    this key which usually is, but need
                                    not be, the record number of a record
                                    in a data file                      }
    Key         : MaxString;      { this is the key.  Although declared
                                    as a string of length 255, the actual
                                    space available is only as much as the
                                    keylength specified when making the
                                    file }
    end;

const












  MaxPageMem  : word = 16384;     { Maximum memory which will be allo-
                                    cated for the page stack -- see above.
                                    This variable is dynamic, and can be
                                    adjusted by a calling program if need
                                    be.                                 }
  MinPageMem  : word = 2048;      { Minimum heap memory which MUST be
                                    available for the page stack. This
                                    amount should be at least equal to the
                                    amount of memory required to hold one
                                    page from each level of the tree plus
                                    one page, each with its full comple-
                                    ment of keys.                       }

var
  OK          : boolean;          { status variable, true if all went
                                    well, false otherwise.              }
  IOError     : integer;          { if an IO error occured, this variable
                                    will contain the error number, or -1
                                    if the error is due to lack of
                                    memory.                             }

procedure MakeFile (var DatF     : DataFile;
                        FileName : Str80;
                        RecLen   : word);

(*   This procedure creates a new data file named 'FileName' and having
a record length of 'RecLen.'   Note that 'RecLen' is declared as type
word, and thus the maximum record size allowed for a BTree4 data file
is 65535 bytes.  Because of possible inaccuracies in counting the size
of record variables it is recommended that programmers us the 'sizeof'
function to pass the record length.  The specified record length is
stored in the file header in record 0, and will always be used when the
file is opened.  The minimum record length is 16 bytes and if 'RecLen'
is less than this, a record length of 16 will be used.  If OK is false
on return, an IO error occured.  *)

procedure OpenFile (var DatF     : DataFile;
                        FileName : Str80);

(*   This procedure opens the fles specified by 'FileName' as a data file
and assigns the file to the variable 'DatF.'  Note that unlike the Data-
base Toolbox, no record length is passed, as the record length is fixed
when making the file, and is extracted when the file is opened.  If OK
is false on return, an IO error occured.  *)

procedure PutRec (var DatF   : DataFile;
                      RecNum : longint;
                  var Buffer            );

(*   This procedure takes 'RecLen' number of bytes from the variable
'Buffer' and writes it to the file as record number 'RecNum.'  If
'Buffer' is not large enough to fill the disk record, extra garbage
will also be written.  If OK is false on return, an IO error occured.  *)













procedure AddRec (var DatF   : DataFile;
                  var RecNum : longint;
                  var Buffer          );

(*   This procedure will add a record to the file 'DatF' containing the
data from the variable 'Buffer.'  'RecNum' will return the number of the
record added.  The new record may be at the end of the file, but need not
be.  As records are deleted from the file they are not physically removed
byt are simply put in a list of available records, and when a new record
is needed the most recently deleted record is used.  The free list is
maintained by a linked list which uses the first four bytes of each
deleted file record.  It is recommended that these four bytes be reserved
specifically for this use, so that a non-zero number in this position
would indicate a free record, and a zero value would indicate a record in
use.  This is useful both in "packing" a data file, and in re-creating
an index file.  If OK is false upon return an IO error occured.  *)

procedure GetRec (var DatF   : DataFile;
                      RecNum : longint;
                  var Buffer            );

(*   This procedure reads the record number RecNum from the previously
opened file DatF and places it into 'Buffer.'  It is the programmer's
responsibility to insure that the variable passed as 'Buffer' is long
enough to hold all the data, otherwise the procedure will possibly over-
write other variables.   If OK is false upon return, an IO error occured.
*)

procedure DeleteRec (var DatF   : DataFile;
                         RecNum : longint);

(*   This procedure places the record specified by 'RecNum' on the list
of available records, and fills the first four bytes of the record with
$FFFFFFFF.  The next time a new record is added to the file, one of the
from the available list will be used, and overwritten.  If OK is false
upon return, an IO error has occurred.  *)

procedure CloseFile (var DatF : DataFile);

(*   This procedure updates the file header information and closes the
file.  The file is closed even if an IO error occured while trying to
save the header information.  The information remains, of course, in the
file variable, until it is re-used, and may be extracted by an error
handling routine.  If OK is false upon return, an IO error occured.  *)

function FileLen (var DatF : DataFile) : longint;

(*   Similar to the Database Toolbox, this function returns the number of
records in DatF, both used and available.  This function is equivilent to
"FileSize (DatF.F)" which can be used alternatively with less overhead.
*)

function UsedRecs (var DatF : DataFile) : longint;













(*   Included primarily for compatability with the Database Toolbox, this
function returns the number of used (non-available) records in the file.
It is functionally equivilent to "FileSize (DatF.F) - DatF.NumberFree."
*)

procedure MakeIndex (var IdxF         : IndexFile;
                         FileName     : Str80;
                         KeyLength,
                         KeysPerPage  : byte);

(*   This procedure will create a new index file named 'FileName.'  It is
similar to the procedure MakeFile, but instead of specifying the record
length the programmer specifies the maximum length of a key ('KeyLength')
and the maximum number of keys that can be placed on one page.  This
information is used to calculate the record length which is
5 + (KeysPerPage * (KeyLength + 9)).  In addition to calculating the
record length, this procedure initializes other data necessary to use
as an index file.  Note that unlike the Database Toolbox it is not neces-
sary to indicate if duplicate keys are allowed, as duplicate keys are
always allowed in BTree4. If OK is false upon return, an IO error occured.
*)

procedure OpenIndex (var IdxF     : IndexFile;
                         FileName : Str80);

(*   This procedure opens the index specified by 'FileName' and initial-
izes certain necessary data elements.  Note than information about the
keys is not required as this information has been saved in the header
in record 0.  *)

procedure CheckMem (Needed : word);

(*   This procedure checks the amount of memory on the heap used by the
page stack, and if it is greater than that specified in the global vari-
able 'MaxPageMem' plus that specified by 'Needed', little used pages, and
their children, are removed from memory.  If the amount needed does not
exceed 'MaxPageSize', but does exceed the maximum available memory, little
used pages will be removed, until the amount needed is available, or until
the stack size reaches 'MinPageMem'.  If the amount of memory needed
cannot be made available, OK will be set to false, and IOError will be set
to -1.   *)

procedure AddKey (var IdxF     : IndexFile;
                  var RefAdded : longint;
                      KeyAdded : MaxString);

(*   This procedure places the key passed as 'KeyAdded' into the index
tree at the proper place in order.  If the length of the key passed is
greater than that allowed for the index file, the key passed will be
truncated.  The procedure gives no warning if a duplicate key is added,
as duplicate keys are always allowed.  If the data reference is the
same for both keys, the second one is not added, otherwise it is.  If
you want to eliminate duplicate keys you must use the FindKey procedure
before adding a key.  If OK is false upon return, an IO error has occured.












*)

procedure FindKey (var IdxF      : IndexFile;
                   var RefFound  : longint;
                       KeySought : MaxString);

(*   This procedure searches the index file for the FIRST occurance of
the key sought.  If the length of the key passed is greater than that
allowed for the index file, the key passed will be truncated.  If the
key is found OK will be true upon return.  If OK is false and IOError
is not zero then an IO error has occured.  *)

procedure SearchKey (var IdxF      : IndexFile;
                     var RefFound  : longint;
                     var KeySought : MaxString);

(*   Similar to FindKey, this procedure searches the index file for the
first key which is equal to OR greater than 'KeySought.'  'KeySought'
will return the value of the key found, and RefFound will return its
reference.  If upon return OK is false and IOError is zero then there
are no keys in the index file greater than or equal to the key sought. *)

procedure NextKey (var IdxF      : IndexFile;
                   var RefFound  : longint;
                   var KeySought : MaxString);

(*   This procedure will find the next key in the file after a call to
any of the search procedures.  This procedure is used to perform a
sequential search of index file.  To set the file to the beginning,
use the procedure ClearKey.  After adding a record, a call to NextKey
will find the key immediately after the key added.  'KeySought' will
return the value of the key found, and RefFound will return its refer-
ence.  If upon return OK is false but IOError is zero the end of the
file has been reached.  Another call to NextKey at this point will
return the first key in the index.  *)

procedure PrevKey (var IdxF      : IndexFile;
                   var RefFound  : longint;
                   var KeySought : MaxString);

(*   This procedure will find the key in the index file which is previous
in order to the key last referenced.  This procedure is used to perform
a reverse sequential search on the file.  To set the file to the end of
the index use the the procedure ClearKey.  After adding a record, a call
to PrevKey will find the key immediately prior to the key added.
'KeySought' will return the value of the key found, and RefFound will
return its reference.  If upon return OK is false but IOError is zero,
the beginning of the file has been reached.  Another call to PrevKey at
this point will return the last key in the index.  *)

procedure ClearKey (var IdxF : IndexFile);

(*   This procedure sets the current index file position to the beginning
(or end) of the index file.  After calling clear key a call to NextKey












will return the first key in the index, and a call to PrevKey will return
the last key in the index.  *)

procedure DeleteKey (var IdxF    : IndexFile;
                         DataRef : longint;
                         Key     : MaxString);

(*     This procedure removes a key from the index file, if it matches
'Key' AND 'DataRef'.  The double check is required because duplicate keys
may exist in the index file, but not duplicate keys with the same data
reference.  If the deletion of a key causes a page to have fewer than
'KeysPerPage' divided by two keys on the page, the page will be merged
with a sibling.  If all keys are removed from the entire indexfile it
will not be deleted, but will exist with only the header record.  *)

procedure CloseIndex (var IdxF : IndexFile);

(*   This procedure will update the header information and close the
index file specified.  In addition, all pages currently in memory which
were read from this file are purged and the memory is returned to the
heap.  Like CloseFile, the file is closed even if the header information
was not successfully saved, and an examination of the File variable will
be necessary to save the information.  *)

procedure Unlink (var Link;
                  var Head;
                  var Tail);

(*   This procedure is a special bonus.  Unlink is used to maintain double
linked lists of records on the heap, where the first four bytes of the
record is a pointer to the next record, and the next four bytes is a
pointer to the previous record.  The three parameters passed MUST be
pointer types; 'Link' is a pointer to the record to be unlinked; 'Head'
is the pointer to the head end of the linked list; and 'Tail' is the
pointer to the tail end of the list.  Calling Unlink removes the record
pointed to by 'Link' from the linked list, re-establishing all links,
and updating the head pointer or tail pointer if necessary.  None of
the pointers in 'Link^' are affected.  *)


     BTree4 is  shareware, which  means that it, like most shareware, may be
freely copied and distributed so long  as no  consideration is  required for
its distribution,  except a  copying and  media charge  not to exceed $3.00,
including the cost of the means of distribution (i.e., diskette).  Users who
find the  program of  value to  them should  consider sending  a donation to
Pass-Key Software.

     Users sending a donation of $25.00 or more are registered, will receive
notification of upgrades and modifications to this product, and are entitled
to receive source code and future updates, upon request, for  the cost  of a
diskette and  postage.   Non-registered useres may not incorporate this unit
into  any  commercially  distributed  software,  including  shareware, while
registered users may do so freely.













     BTree4 is  a copyrighted  program, and  is protected by the laws of the
United States and each of its several states.  A  licence is  hereby granted
to all  persons to  use this program according to the terms and restrictions
contained herein.  All programs which  incorporate all  or any  part of this
program must include the following phrase both in the source code and in any
accompanying documentation:

     Portions of this program Copyright (c) 1988 by W. Lee Passey.

     This program is distributed as is, and by its use each person agrees to
the  terms  and  conditions  of  this  license, and acknowledges that W. Lee
Passey and Pass-Key Software have  made  no  warranties,  either  express or
implied,  concerning  the  performance  of  this software, including that of
fitness for a particular purpose.

     Please send all comments,  suggestions, information  regarding possible
bugs, donations and registration information to:

                             Pass-Key Software
                            119 MacArthur Ave.
                         Salt Lake City, UT  84115

or use  your modem  to call The Motherboard, [phone], 8 data, 1 stop,
no parity, 300/1200/2400 baud, 24 hours/day, 7 days/week.

     I am also looking for a job in the data processing field, and this unit
is a good example of my programming skills.  If any employers are interested
in using me as an employee, please contact me in the same way.